// https://www.lintcode.com/problem/79/

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        int m = A.length();
        int n = B.length();
        int max_val = 0;
        vector<vector<int>> rec(m + 1, vector<int>(n + 1, 0));
        // rec[i][j] 表示以A[i - 1] & B[j - 1]结尾的最长公共子串 注意和最长公共子序列的区别
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (A[i - 1] == B[j - 1]) {
                    rec[i][j] = rec[i - 1][j - 1] + 1;
                    max_val = max(max_val, rec[i][j]);
                }
                else rec[i][j] = 0; //注意和最长公共子序列的区别
            }
        }
        return max_val;
    }
};